{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.6 The CHSH Game\n",
    "\n",
    "* [Q# exercise: CHSH Game](./1-Basic_Quantum_Concepts/6-CHSH_Game.ipynb#qchsh)\n",
    "\n",
    "The CHSH Game sheds more light on the nature of quantum entanglement and helps us understand that\n",
    "entanglement really is \"spooky action at a distance,\" as Albert Einstein called it. The CHSH Game is named\n",
    "for four physicists who discovered the [CHSH Inequality](https://en.wikipedia.org/wiki/CHSH_inequality): John Clauser, Michael Horne, Abner Shimony, and\n",
    "Richard Holt. In essence, the CHSH Game/Inequality illustrates that quantum entanglement cannot be\n",
    "explained by a [local hidden-variable theory](https://en.wikipedia.org/wiki/Local_hidden-variable_theory). For quantum computing, this is another algorithm where we\n",
    "can employ a feature of quantum mechanics to yield a solution that is more efficient than any classical\n",
    "solution.\n",
    "\n",
    "The game is played as follows:\n",
    "\n",
    "![Figure CHSHGame](media/CHSH_game.png)\n",
    "\n",
    "Alice and Bob are physically separated and not allowed to communicate with one another, during\n",
    "the game. (They are allowed to set a strategy together before the game begins and share entangled qubits,\n",
    "however). The Referee sends a uniformly random bit x to Alice and a uniformly random bit y to Bob.\n",
    "Then, Alice and Bob send back their respective answer bits, a and b, based on the strategy they set ahead\n",
    "of time.\n",
    "\n",
    "Alice and Bob win the game if a $\\oplus$ b = x $\\cdot$ y.  So, if either x or y is 0, then a and b should be the\n",
    "same, but if x and y are both one, then a and b should be different.\n",
    "\n",
    "If we look at the classical solution first, suppose Alice and Bob decide on a trivial strategy of always\n",
    "returning 0 for both a and b. Then, we can see that they will win at most 75% of the rounds of the game\n",
    "(on average):\n",
    "\n",
    "<table>\n",
    "  <tr>\n",
    "    <th>x &nbsp; &nbsp; &nbsp; </th>\n",
    "    <th>y &nbsp; &nbsp; &nbsp; </th>\n",
    "    <th>x &sdot; y &nbsp; &nbsp; </th>\n",
    "    <th>a &nbsp; &nbsp; &nbsp; </th>\n",
    "    <th>b &nbsp; &nbsp; &nbsp; </th>\n",
    "    <th>a &oplus; b &nbsp; &nbsp; </th>\n",
    "    <th>result </th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> win </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 0 </td>\n",
    "    <td> 1 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> win </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 1 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> win </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 1 </td>\n",
    "    <td> 1 </td>\n",
    "    <td> 1 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "    <td> loss </td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "\n",
    "\n",
    "But if we dig into the classical case further, we can see that no matter what function of x or y that\n",
    "we pick, to yield a and b, we can't win more than 75% of the time, because of the difference between the\n",
    "first three rows and the last row. What if we employ a quantum strategy, based on a shared pair of\n",
    "entangled qubits that are in a Bell state $\\frac{|00\\rangle + |11\\rangle}{\\sqrt 2}$?\n",
    "\n",
    "If x = 0, then Alice measures her entangled qubit in the |0⟩ basis and if her measurement is |0⟩\n",
    "then she returns a = 0 and if her measurement is |1⟩ then she returns a = 1. If x = 1, then Alice\n",
    "measures her entangled qubit in the |+⟩ basis and if her measurement is |+⟩ then she returns a = 0\n",
    "and if her measurement is |−⟩ then she returns a = 1. If y = 0, then Bob measures his entangled\n",
    "qubit in the |x⟩ basis, rotated by $\\frac{\\pi}{8}$ , and if his measurement is |$\\frac{\\pi}{8}\\rangle$ then he returns b = 0 and if his\n",
    "measurement is |$\\frac{-\\pi}{8}\\rangle$ then he returns b = 1. If y = 1, then Bob measures his entangled qubit in the\n",
    "|x⟩ basis, rotated by $\\frac{-\\pi}{8}$; and if his measurement is |$\\frac{-\\pi}{8}\\rangle$ then he returns b = 0 and if his measurement\n",
    "is |$\\frac{\\pi}{8}\\rangle$ then he returns b = 1, where\n",
    "\n",
    "|$\\frac{\\pi}{8}\\rangle = \\cos (\\frac{\\pi}{8}) |0\\rangle + \\sin (\\frac{\\pi}{8}) |1\\rangle $\n",
    "\n",
    "|$\\frac{-\\pi}{8}\\rangle = \\cos (\\frac{-\\pi}{8}) |0\\rangle + \\sin (\\frac{-\\pi}{8}) |1\\rangle $\n",
    "\n",
    "Let's take a look at how well this quantum strategy works. We can look at two different cases:\n",
    "Case(1) is the first three rows in the table above (where the classical a = b = 0 strategy wins all of the\n",
    "time) and Case(2) is the last row in the table, where the classical strategy loses all of the time.\n",
    "\n",
    "Case(1):\n",
    "\n",
    "Suppose that Alice has x = 0 and she measures |0⟩ meaning that she will return a = 0. So, they will\n",
    "win if Bob outputs b = 0. We know that Bob's qubit is in the |0⟩ state, because it is entangled with\n",
    "Alice's which already measured |0⟩. So Bob will measure |0⟩ in a basis rotated by $\\frac{\\pi}{8}$, and he outputs b =\n",
    "0 if he measures |$\\frac{\\pi}{8}\\rangle$ and the probability that Bob does this is $\\cos^2 (\\frac{\\pi}{8})$ ≈ 85%.\n",
    "\n",
    "Case(2):\n",
    "\n",
    "Now, Alice gets x = 1 and measures her entangled qubit in the |+⟩ basis and suppose she gets |+⟩\n",
    "meaning that she will return a = 0. So, they will win if Bob outputs b = 1. We know that Bob's qubit\n",
    "is in the |+⟩ state, so Bob will measure |+⟩ in a basis rotated by $\\frac{-\\pi}{8}$, because y = 1 in this case. So, the\n",
    "probability of getting $\\frac{\\pi}{8}$ as a result of Bob's measurement is the angle between |+⟩ and $\\frac{\\pi}{8}$ which is\n",
    "$\\cos^2 (\\frac{\\pi}{8})$ ≈ 85%.\n",
    "\n",
    "If Alice and Bob employ the quantum strategy, their chances of winning the CHSH Game improve\n",
    "by 10%, going up from 75% to 85%. Those are good odds!\n",
    "\n",
    "\n",
    "\n",
    "**CHSH Game example in Quirk**\n",
    "\n",
    "If you open the [CHSH Game example](https://algassert.com/quirk#circuit=%7B%22cols%22:%5B%5B%22H%22%5D,%5B%22%E2%97%A6%22,1,1,1,%22X%22%5D,%5B%22X%5E-%C2%BC%22%5D,%5B%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22%5D,%5B%22%7Eda85%22,%22%7E5s2n%22,1,%22%7E5s2n%22,%22%7Eahov%22%5D,%5B1,%22H%22,1,%22H%22%5D,%5B1,%22Measure%22,1,%22Measure%22%5D,%5B%22X%5E%C2%BD%22,%22%E2%80%A2%22%5D,%5B1,1,1,%22%E2%80%A2%22,%22X%5E%C2%BD%22%5D,%5B%22Measure%22,1,1,1,%22Measure%22%5D,%5B%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22%5D,%5B1,%22%E2%80%A2%22,%22X%22,%22%E2%80%A2%22%5D,%5B%22%E2%80%A2%22,1,%22X%22%5D,%5B1,1,%22X%22,1,%22%E2%80%A2%22%5D,%5B1,1,%22Chance%22%5D,%5B1,1,%22%7Eq6e%22%5D%5D,%22gates%22:%5B%7B%22id%22:%22%7Eda85%22,%22name%22:%22Alice%22,%22matrix%22:%22%7B%7B1,0%7D,%7B0,1%7D%7D%22%7D,%7B%22id%22:%22%7Eahov%22,%22name%22:%22Bob%22,%22matrix%22:%22%7B%7B1,0%7D,%7B0,1%7D%7D%22%7D,%7B%22id%22:%22%7E5s2n%22,%22name%22:%22Referee%22,%22matrix%22:%22%7B%7B1,0%7D,%7B0,1%7D%7D%22%7D,%7B%22id%22:%22%7Eq6e%22,%22name%22:%22Win?%22,%22matrix%22:%22%7B%7B1,0%7D,%7B0,1%7D%7D%22%7D%5D%7D) in Quirk, you will see this implementation:\n",
    "\n",
    "![Figure CHSHGameQuirk](media/CHSH_game_quirk.png)\n",
    "\n",
    "\n",
    "The top wire is Alice's entangled qubit and the bottom wire is Bob's—which compute a and b,\n",
    "respectively. The second and the fourth wire are the Referee's qubits, x and y, respectively. The\n",
    "combination of the H gate and a measurement is a coin flip, so that is how the Referee sends random bits\n",
    "to Alice and Bob. You can see that Alice's and Bob's computations don't communicate, because Alice's\n",
    "and Bob's computations are carried out between the ellipses (...) on Alice's and Bob's wires and there are\n",
    "no control wires linking those two wires. Finally, the controlled-Not gates after the final ellipses (...) are\n",
    "how the results are scored. We see the 85% chance of winning with the Quantum solution (the classical\n",
    "solution isn't represented here).\n",
    "\n",
    "\n",
    "### Q# exercise: CHSH Game\n<a id='#qchsh'></a>",
    "\n",
    "There are also Q# Kata for the CHSH Game available here, for the Visual Studio/Visual Studio Code versions\n",
    "and available here for the Binder Q# notebook version.\n",
    "\n",
    "**_Further Reading_**\n",
    "\n",
    "A Quantum computing [lecture](https://cs.uwaterloo.ca/~watrous/CPSC519/LectureNotes/20.pdf) by John Watrous. A pair of lectures ([here](https://www.scottaaronson.com/qclec/13.pdf) and [here](https://www.scottaaronson.com/qclec/14.pdf)) by Scott Aaronson.\n",
    "And an entry from the [Quantum Gazette](https://quantumgazette.blogspot.com/2016/07/chsh-game-and-quantum-entanglement.html).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python38332bit225b1603132a4a1f9abff16033481403",
   "display_name": "Python 3.8.3 32-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}